All natural numbers greater than 1 have a unique prime factorization.
GCD is the greatest common divisor.
LCM is the least common multiple.
$${a = p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots p_n^{k_n} }$$
$${b = p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots p_n^{m_n} }$$
$${\text{gcd}(a,b) = p_1^{\text{min}(k_1,m_1)} p_2^{\text{min}(k_2,m_2)} \cdots p_n^{\text{min}(k_n,m_n)} }$$
$${\text{lcm}(a,b) = p_1^{\text{max}(k_1,m_1)} p_2^{\text{max}(k_2,m_2)} \cdots p_n^{\text{max}(k_n,m_n)} }$$
$${a = p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots p_m^{k_m} }$$
$${n = \text{number of divisors} = (k_1 + 1)(k_2 + 1) (k_3 + 1) \cdots (k_m + 1) }$$
$${\text{product of divisors} = a^{n/2} }$$
$${\text{sum of divisors} = \frac{p_1^{k_1 + 1} - 1}{p_1 - 1} \frac{p_2^{k_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_m^{k_m + 1} - 1}{p_m - 1} }$$
$${\text{if } a \mid b }$$
$${\text{then }an = b }$$
$${\text{if } a \mid b \text{ and } b \mid c }$$
$${\text{then } a \mid c }$$
$${\text{if } a \mid b \text{ and } b \mid a }$$
$${\text{then } a = b }$$
$${\text{if } d \mid a \text{ and } d \mid b }$$
$${\text{then } d \mid (ax + by) }$$
$${\text{if } d \mid a }$$
$${\text{then } dn \mid an }$$
$${\text{if } dn \mid an }$$
$${\text{then } d \mid a }$$
$${\text{if } d \mid a }$$
$${\text{then } \frac{a}{d} \mid a }$$
2
Divisibility by 2 requires that the number is even.
3
Divisibility by 3 requires that sum of the digits is divisible by 3.
4
Divisibility by 4 requires that the last 2 digits are divisible by 4.
5
Divisibility by 5 requires that last digit is either 5 or 0.
6
Divisibility by 6 requires that number is even and divisible by 3.
7
For 7 take the first 2 digits from the left and replace those 2 digits with that 2 digit number mod 7.
Repeat this process until you can determine if the remaining number can be divided by 7 .
8
Divisibility by 8 requires that the last 3 digits are divisible by 8.
9
Divisibility by 9 requires that sum of the digits is divisible by 9.
10
Divisibility by 5 requires that last digit is 0.
11
Divisibility by 11 requires that alternating sum of the digits (from either side) is divisible by 11.
12
Divisibility by 12 requires that number is divisible by 3 and 4.
14
Divisibility by 14 requires that number is divisible by 2 and 7.
15
Divisibility by 15 requires that number is divisible by 3 and 5.
37
Take the number in groups of 3 digits from right to left and add them together. If the result is divisible by 37 then the number is divisible by 37.
$${\text{if } a \equiv b {\pmod n} }$$
$${\text{then } n \mid a - b }$$
$${\text{if } a \equiv b {\pmod n} \text{ and } d \mid n }$$
$${\text{then } a \equiv b {\pmod d} }$$
$${\text{if } a \equiv b {\pmod n} }$$
$${\text{then } ac \equiv bc {\pmod {nc}} }$$
$${\text{if } a \equiv b {\pmod n} }$$
$${\text{then } a^k \equiv b^k {\pmod n} }$$
If a and n are relatively prime then there is a solution for \(a^{-1} {\pmod {n}} \)
The inverse can be found using Bezout's identity for gcd(a,n) = 1:
$${ax + by = 1}$$
For difficult inverses with large numbers it is recommended to use the Euclidean Algorithm.
You can also use the following formula to find the inverse:
$${a^{-1} {\pmod {n}} = a^{\phi(n) - 1} {\pmod {n}}}$$
Sophie-Germain Primes
A prime p where 2p + 1 is also a prime.
Example 11 is a Sophie-Germain prime because 23 is also prime.
The resulting prime from 2p + 1 (in this case 23) is called a safe prime.
Fermat Primes
A Fermat number is defined as \(F_n = 2^{2^n} + 1 \)
A Fermat prime is just a prime Fermat number.
There are only 5 Fermat primes:
\(F_0 = 3, F_1 = 5,F_2 = 17,F_3 = 257,F_4 = 65537\)
And these are the only primes of the form \(2^n + 1 \)
Fibonacci Primes
Fibonacci Primes are just primes within the Fibonacci Sequence:
1,1,2,3,5,8,13,21,34,55...
An interesting result is that Fibonacci Primes also have a prime index except for 4.
This is because in the Fibonacci sequence:
$${a \mid b \to F_a \mid F_b}$$
But not every Fibonacci number with a prime index is a prime.
So the first few Fibonacci Primes are:
$${F_3=2, F_4=3, F_5=5, F_7 = 13, F_{11} = 89, \cdots }$$
Mersenne Primes
Mersenne Primes are of the form \(2^n - 1\) where n is prime.
Some examples: 3, 7, 31, 127...
The value of n must be prime but it doesn't gaurantee a prime since \(2^{11} - 1 = 2047 = 23 \cdot 89 \)
Pythagorean Primes
Pythagorean Primes are primes of the form \(4^n + 1\) where n > 0.
Some examples: 5, 7, 13, 17, 29, 37...
These primes are related to the Pythagorean theorem and Sum of Two Squares.
All primes of the form \(4^n + 1\) can be expressed exactly one way as a sum of two squares (unordered, non-negative integers)
Then by Pythagorean theorem there is a right triangle with hypotenuse \(\sqrt{p}\) where p is a Pythagorean prime and the other sides are both integer length.
A natural number n greater than 1 is a prime if and only if \( (n - 1)! \equiv n-1 {\pmod n} \)
$${(p - 1)! \equiv p-1 {\pmod p} \equiv -1 {\pmod p} }$$
$${(p - 2)! \equiv 1 {\pmod p} }$$
$${(p - 3)! \equiv (p-2)^{-1} {\pmod p} \equiv (-2)^{-1} {\pmod p} }$$
$${(p - k)! \equiv (p-2)^{-1} (p-3)^{-1} \cdots (p-k+1)^{-1} {\pmod p}, k > 2 }$$
$${(p - k)! \equiv (-2)^{-1} (-3)^{-1} \cdots (1-k)^{-1} {\pmod p}, k > 2 }$$
For integers a and b with greatest common divisor d there exists integers x and y such that \( ax + by = d \).
For prime number p where \(p \nmid a \) :
$${a^{p-1} \equiv 1 {\pmod p} }$$
$${a^{p} \equiv a {\pmod p} }$$
Assume n has the prime factorization: \(n = p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots \)
$${\phi(n) = n \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \frac{p_3 - 1}{p_3} \cdots }$$
$${\phi(n) = p_1^{k_1 - 1} (p_1 - 1) p_2^{k_2 - 1} (p_2 - 1) p_3^{k_3 - 1} (p_3 - 1)\cdots }$$
$${\phi(mn) = \phi(m) \phi(n) \text{ if } gcd(m,n) = 1}$$
$${\phi(2^n) = \frac{2^n}{2} = 2^{n-1} }$$
$${\phi(n) = \phi(2^k 3^m) = \frac{n}{3} }$$
For a single prime p: \(\phi(p) = p - 1 \)
Divisor Sum:
$${\sum_{d \mid n}^{} \phi(d) = n }$$
$${a^{\phi(n)} \equiv 1 {\pmod n} \text{ if } gcd(a,n) = 1}$$
The Carmichael function of n is the smallest value of m such that \(a^{m} \equiv 1 {\pmod n}, \text{gcd}(a,n) = 1 \) for every a.
$${\lambda(n) = \begin{cases} \phi(n) & n = 1,2,4,p^k \\ \frac{1}{2} \phi(n) = \cfrac{n}{4} & n = 2^k, k > 2 \\ \text{lcm}\left(\lambda(n_1),\lambda(n_2),\lambda(n_3), \cdots \right) & n_k = \text{powers of distinct primes} \end{cases} }$$
$${\lambda(n) = \phi(n) \text { for } n = 1,2,4,p^k, 2 p^k }$$
$${\lambda(n) \mid \phi(n) \ \forall \ n }$$
Vanishing 2's and 3's:
$${\lambda(2^a 3^b n_1 n_2 \cdots n_k) = \lambda(n_1 n_2 \cdots n_k), a < 4, b < 2, k > 0, n_k = \text{powers of distinct primes}}$$
$${\lambda(2^a 3^b) = \lambda(3^b), a < 4}$$
$${\lambda(3 \cdot 2^a) = \lambda(2^a)}$$
The order of a mod m is the least value of m such that:
$${a^{m} \equiv 1 {\pmod n}}$$
We express the order of a mod m like \(\text{ord}_m(a) \)
$${\text{ord}_n(a) = 0 \iff \text{gcd}(a,n) \ne 1}$$
$${\text{ord}_n(a) \mid \phi(n)}$$
$${\text{ord}_n(a^k) = \frac{\text{ord}_n(a)}{\text{gcd}(k,\text{ord}_n(a))} }$$
For prime p when \(d \mid p-1\) then there are \( \phi(d) \) numbers of order d.
$${\text{ind}_a(a) = 1}$$
$${\text{ind}(ab) = \text{ind}(a) + \text{ind}(b) \pmod{\phi(n)}}$$
$${\text{ind}(a^n) = n \ \text{ind}(a) \pmod{\phi(n)}}$$
$${\text{ind}(-1) = \frac{\phi(n)}{2}}$$
$${\text{ind}(1) \equiv 0 \pmod{\phi(n)}}$$
We say a is a primitive root mod n when:
$${\text{ord}_n(a) = \phi(n)}$$
This only happens when:
$${\lambda(n) = \phi(n) \text { for } n = 1,2,4,p^k, 2 p^k }$$
where p is an odd prime.
Every prime number has primitive roots.
Every composite of multiple distinct odd primes has no primitive roots.
If there exists primitive roots the number that exist will always be \(\phi(\phi(n)) \)
Primitive roots exist only for \(1,2,4,p^k,2p^k\) where p is an odd prime.
If r is a primitive root mod p where p is prime then \(r^k\) will acheive all possible residues mod p.
More generally, if r is a primitive root mod n then \(r^k\) will acheive all values of m where 0 < m < n where gcd(m,n) = 1.
If r is a primitive root mod n then \(r^k\) is a primitive root \( \iff \text{gcd}(k,\phi(n) = 1) \).
If r is a primitive root mod p then \(r^{\frac{p-1}{q}} \not \equiv 1 \pmod{p} \ \forall \ q \mid p-1 \) where q and p are prime.
In other words: you only need to check the prime divisors, not all divisors of the totient.
Note: p must be prime. For composites you need to check against primes and then boost it.
If r is a primitive root mod p then \(r^{\frac{p-1}{2}} \equiv -1 \pmod{p} \) where p is prime.
If r is a primitive root mod p and \(p^2\) then it is also a primitive root mod \(p^k\)
If r is a primitive root mod p then r + mp is also a primitive root mod \(p^k\) for at least one of m = 0 or 1.
Note: this is "usually" true for both m = 0 and 1 and larger integers but it's not 100% reliable. For example:
2 is a primitive root mod 5 but 2 + 5 = 7 but 7 is not a primitive root mod 25
If r is a primitive root mod \(p^k\) and it is odd then it is also a primitive root mod \(2p^k\)
If r is a primitive root mod \(p^k\) and it is even then \(r + p^k\) is also a primitive root mod \(2p^k\)
For a prime p the product of all primitive roots mod p is equal to 1 mod p.
$${r^a \equiv r^b {\pmod n} \iff a \equiv b \pmod{\phi(n)} }$$
We say a number is a quadratic residue if there is a solution to the equation:
$${x^2 \equiv a {\pmod n}}$$
For prime p the number of quadratic residues and non-residues is the same and equal to \( \frac{p-1}{2} \)
Quadratic residues can never be primitive roots.
Non-primitive roots can be either quadratic residues or non-residues
The legendre symbol \( \left( \frac{a}{p} \right) \) can be read as "Is a a quadratic residue mod p?"
For the legendre symbol p must be an odd prime.
$${\left( \frac{a}{p} \right) = \left( \frac{b}{p} \right) \iff a \equiv b \pmod p }$$
Euler's Criterion
$${\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} {\pmod p}}$$
Formulas
$${\left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) }$$
$${\left( \frac{a^2}{p} \right) = 1 }$$
$${\left( \frac{1}{p} \right) = 1 }$$
$${\left( \frac{a^{2k}}{p} \right) = 1 }$$
$${\left( \frac{a^{2k+1}}{p} \right) = \left( \frac{a}{p} \right) }$$
$${\left( \frac{-1}{p} \right) = \begin{cases} 1 & p \equiv 1 \pmod 4 \\ -1 & p \equiv 3 \pmod 4 \end{cases}}$$
$${\left( \frac{-a^2}{p} \right) = \begin{cases} 1 & p \equiv 1 \pmod 4 \\ -1 & p \equiv 3 \pmod 4 \end{cases}}$$
$${\left( \frac{2}{p} \right) = \begin{cases} 1 & p \equiv \pm 1 \pmod 8 \\ -1 & p \not \equiv \pm 1 \pmod 8 \end{cases}}$$
$${\left( \frac{3}{p} \right) = \begin{cases} 1 & p \equiv \pm 1 \pmod{12} \\ -1 & p \not \equiv \pm 1 \pmod{12} \end{cases}}$$
$${\left( \frac{5}{p} \right) = \begin{cases} 1 & p \equiv \pm 1 \pmod 5 \\ -1 & p \not \equiv \pm 1 \pmod 5 \end{cases}}$$
For odd prime p ONLY:
$${\text{# of quadratic residues} = \text{# of non-residues} = \frac{p-1}{2}}$$
Quadratic Reciprocity
Where p and q are primes:
$${\left( \frac{p}{q} \right) = \begin{cases} \left( \frac{q}{p} \right) & p \text{ or } q \equiv 1 \pmod 4 \\ -\left( \frac{q}{p} \right) & p \text{ and } q \equiv 3 \pmod 4 \end{cases}}$$
$${(a^2 + b^2) (c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2 = (ac - bd)^2 + (ad + bc)^2 }$$
Interpretation: the product of 2 numbers that can be expressed as a sum of squares can also we expressed as a sum of 2 squares.
Notice that it also implies it can be expressed 2 ways assuming \(a \not = b\) and \(c \not = d\) and \(a, b \not = 0\).
A positive integer can be expressed as the sum of 2 squares if none of it's prime factors of the form 4k + 3 have an odd exponent.
Jacobi 2 Squares Theorem
$${d_1 = \text{# of factors 1 mod 4}}$$
$${d_3 = \text{# of factors 3 mod 4}}$$
$${r_2(n) = 4 (d_1(n) - d_3(n)) }$$
This tells you the number of ways a number can be expressed as the sum of 2 squares.
Note: this includes negative values and it counts different orderings.
For the unordered result that only uses values greater than or equal to zero:
$${n = 2^k \cdot p_1^{a_1} \cdots p_r^{a_r} \cdot q_1^{b_1} \cdots q_s^{b_s} }$$
$${p_i \equiv 1 \pmod 4 }$$
$${q_j \equiv 3 \pmod 4 }$$
$${r(n) = \left\lceil \frac{1}{2} (a_1+1)(a_2+1)\cdots (a_r+1) \right\rceil }$$
If any \(b_m\) are odd then the result is zero.
Notice the result is not dependent on the exponent of 2 or any of the exponents on \(q_j\).